This invention relates to apparatus for decoding and decompressing image coded compressed image information. More particularly, this invention relates to apparatus for decoding and decompressing coded compressed image information efficiently and reliably without any back tracking in the input compressed code stream or reference image information.
Imagery which has been rasterized and digitized can be compressed using Huffman coding techniques (reference 1) to encode "features" of the images. Features which are typically encoded are run-lengths of a given color within a given raster line and color change correlation between successive raster lines. Using the Huffman coding technique, these features are encoded into a set of binary codes of variable length based on the statistics of a set of sample images. Examples of this image compression technique are the CCITT Group III and Group IV algorithms. These algorithms are well known in the prior art.
The CCITT Group III and Group IV compression algorithms typically result in a relatively high compression ratio of the number of binary bits contained in the original image to the number of binary bits contained in the compressed image. For black and white (binary pel) imagery containing text, symbols and graphics, the compression ratio can typically range from 5:1 to 50:1. The processing, identification and reconstruction can be performed by software.
The CCITT Group III and Group IV compression algorithms are frequently used to minimize the storage and transmission requirements of equipment which handles scanned images, such as facsimile equipment. Because the image expansion apparatus should produce expanded images at a rate commensurate with the speed of the image output device, such as a printer or raster display, with which it communicates, it is advantageous to utilize high speed image electronics for image decompression. The input rate of image output devices can range from two hundred thousand (200,000) pels (pixels) per second for a facsimile machine to one hundred million (100,000,000) pels (pixels) per second for a laser printer or Cathode Ray Tube (CRT) display.
In order to reconstruct the coded images, known as expansion or decompression, the code stream is processed, individual digital code words identified and the encoded features of the original image reconstructed. CCITT Group III and Group IV decompression has been implemented with software operating on a standard computer or microprocessor. The decompression speed of software operating on microprocessor and using CCITT Group III and Group IV algorithms, while adequate for facsimile equipment, is frequently many times slower than the speed of high speed output devices such as a laser printer. As a result, high speed output equipment must utilize specialized image decompression circuitry.
This invention relates to direct circuit means of decompressing imagery which has been compressed by using CCITT Group III, CCITT Group IV or similar algorithms which employ Huffman coding or modified Huffman coding to compress run lengths of a given color and color change correlation between successive raster lines. Such direct circuit means operates on a digital basis. Such direct circuit means is preferably constructed of identical semiconductor technology as a microprocessor. Because of its specialized structure, such circuit means preferably utilizes a comparable number of logic gates, but achieves a processing speed many times greater than the processing speed obtained by a microprocessor in providing decompression.
In one embodiment of the invention, a code parser decodes coded compressed image information. The image information may be disposed on a document or on a cathode ray tube. A code expander operating asynchronously relative to the code parser decompresses the compressed image information in accordance with the decoding of such information by the code parser. A code window register in the code parser has a length at least as long as the longest code in the coded compressed image information. When the code indicates a compression in one line in a raster scan corresponding (or substantially corresponding) to a compression in a previous line in the raster scan, the reference window register and associated circuitry scan the line and provide for the decompression in the line being scanned in accordance with the decompression at the (substantially) corresponding positions in the preceding line (reference 2).
The associated circuitry may include two memories, one for even scan lines and the other for odd scan lines. Other embodiments of this invention may use a common shared memory to storage. Alternate ones of the memories are activated for information comparison between adjacent lines during alternate line scans. When the same color is to be printed at a number of successive positions in the line being scanned, a counter is set to indicate such number and to count such number as the line is being scanned. During this count, the same color is output.
The code parser requests successive codes from an external source and acknowledges the receipt of such successive codes. The code expander receives new codes and expansion instructions from the code parser and acknowledges the receipt of such codes. Under certain circumstances, the code parser may not operate on the next code until the code expander has decompressed the information represented by the previous code. The code expander provides the decompressed image information at its output.